import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 354.俄罗斯套娃问题
 */
public class Exerciser5 {
    /**
     * 解法二：贪心算法
     */
    public int maxEnvelopes2(int[][] envelopes) {
        // 排序规则：
        // 1. 如果第一个数据是不同的的，那么按照第一个数据的 从小到大进行排序
        // 2. 如果第一个数据是相同额的，那么按照第二个数据的 从大到小进行排序
        Arrays.sort(envelopes,(v1,v2) -> {
            return v1[0] != v2[0] ? v1[0] - v2[0] : v2[1] - v1[1];
        });
        // 排完序之后，只需要根据 第二个数据进行查看是否符合 套娃的条件

        // 贪心 + 二分 ，就如同是 最长递归子序列 那道题的贪心似得
        List<Integer> ret = new ArrayList<>();
        ret.add(envelopes[0][1]);

        for(int i = 1;i < envelopes.length;i++) {
            int b = envelopes[i][1];
            if(b > ret.get(ret.size() - 1)) {
                ret.add(envelopes[i][1]);
            }else {
                int left = 0,right = ret.size() - 1;
                while(left < right) {
                    int mid = (left + right) / 2;
                    if(ret.get(mid) >= b) {
                        right = mid;
                    }else {
                        left = mid + 1;
                    }
                }
                ret.set(left,b);
            }
        }
        return ret.size();
    }


    /**
     * 解法一：动态规划
     */
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes,(v1, v2) -> {
            return v1[0] - v2[0];
        });

        // 动态规划
        int n = envelopes.length;
        // dp[i]: 以i位置为结尾的所有套娃的序列中，最长的序列
        int[] dp = new int[n];
        int ret = 0;
        for(int i = 0;i < n;i++) {
            dp[i] = 1;
            for(int j = 0;j < i;j++) {
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
            ret = Math.max(dp[i],ret);
        }
        return ret;
    }
}
